DMS Colloquium: Dr. Brendan Rooney

Speaker: Dr. Brendan Rooney, Korea Advanced Institute of Science and Technology

Title: Vector Colourings and Graph Homomorphisms

Abstract:  A vector colouring of a graph $X$ is a map from $V(X)$ to vectors on the unit sphere in $\mathbb{R}^m$. The goal is to map adjacent vertices to vectors that are far apart. The vector chromatic number of $X$ is the smallest $t\geq 1$ so that there is a vector colouring $\phi$ for which the inner product of $\phi(u)$ and $\phi(v)$ is at most $-1/(t-1)$, whenever $u$ and $v$ are adjacent.

We look at vector colourings given by representations of a graph on its least eigenspace, and identify a class of graphs for which these colourings are optimal. This leads to a novel approach to proving that a graph is a core, and for proving the non-existence of homomorphisms between pairs of graphs. As an application we give a new proof that the Kneser graphs $K_{n:r}$ for $n\geq 2r+1$ and $q$-Kneser graphs $qK_{n:r}$ for $n\geq 2r+1$ are cores; in particular, a proof that does not require application of the Erd{\H o}s-Ko-Rado Theorem.